/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let m = board.length
  let n = board[0].length
  let visited = new Array(m).fill(0).map(() => new Array(n).fill(false))
  let dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  function backTracking (i, j, k) {
    if (board[i][j] !== word[k]) {
      return false
    } else if (k === word.length - 1) {
      return true
    }
    visited[i][j] = true // 表示以及访问过了
    for (let dir of dirs) {
      let ni = i + dir[0]
      let nj = j + dir[1] // 新的坐标
      if (backTracking(ni, nj, k + 1)) {
        return true // 如果下一个是true 那这个就返回true
      }
    }
    // 如果都不是真的 就让这个设置为未访问过
    visited[i][j] = false
    return false // 返回没找到
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (backTracking(i, j, 0)) {
        return true
      }
    }
  }
  return false
};
exist([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], 'ABCCED')